Coding systems, such as image and video encoders, typically encode associated data for streaming from a source to a destination. A transform, such as the Discrete Cosine Transform (DCT), is traditionally at the center of image and video compression algorithms. Lifting steps, wherein a single sub-band is modified solely as a function of the other sub-bands at each step, can be used to implement the DCT and other transforms permitting perfect reconstruction. An advantage of using lifting steps is that when intermediate operations are performed using integer arithmetic, they can be made exactly reversible.
Lifting steps may have been used to implement a reversible integer approximation of the 4-point DCT. Unfortunately, the resulting implementation would have required many more multiplications than the best known algorithms, and would have produced outputs that were scaled by a factor of two compared to an orthonormal DCT. The latter poses a particular problem for lossless compression. Such implementations would have mixed the low-order bits of the input, which may be mostly uncorrelated random noise, to produce an additional bit of output with high apparent entropy. Since such an implementation would have been applied twice for two-dimensional images, this would have produced one extra bit per pixel of difficult-to-compress data to code versus the orthonormal case.
Other implementations of the DCT may have used a different scale factor for each output to save additional multiplications, since the DCT is often directly followed by a quantization step, which can sometimes absorb these additional scale factors. Unfortunately, there is no extra quantization step when using lossless compression; and even when using lossy compression, non-uniform scaling may complicate any additional processing applied to the transform coefficients before quantization. Embodiments of the present disclosure address these and other issues.